package org.hot100.h236;

/**
 * @Author: wjy
 * @Date: 2022/2/10 16:16
 */
public class Solution {

    public static void main(String[] args) {

    }

    /**
     * 递归解析：
     * 终止条件：
     * 当越过叶节点，则直接返回 null ；
     * 当 root 等于 p, qp,q ，则直接返回 root ；
     *
     * 递推工作：
     * 开启递归左子节点，返回值记为 left ；
     * 开启递归右子节点，返回值记为 right ；
     *
     * 返回值： 根据 left 和 right ，可展开为四种情况；
     * 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,qp,q ，返回 null ；
     * 当 left 和 right 同时不为空 ：说明 p, qp,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
     * 当 left 为空 ，right 不为空 ：p,qp,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
     * p,qp,q 其中一个在 root 的 右子树 中，此时 right 指向 pp（假设为 pp ）；
     * p,qp,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
     * 当 left 不为空 ， right 为空 ：与情况 3. 同理；
     *
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = this.lowestCommonAncestor(root.left, p, q);
        TreeNode right = this.lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null) {
            return null;
        }
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }

        return root;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor2(root.left, p, q);

        TreeNode right = lowestCommonAncestor2(root.right, p, q);

        if (left == null && right == null) {
            return null;
        }
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }

        return root;
    }

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null ||root == p || root == q) {
            return root;
        }

        TreeNode left = this.lowestCommonAncestor3(root.left, p, q);
        TreeNode right = this.lowestCommonAncestor3(root.right, p, q);

        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }

    public TreeNode lowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = this.lowestCommonAncestor4(root.left, p, q);
        TreeNode right = this.lowestCommonAncestor4(root.right, p, q);

        if (left == null && right == null) {
            return null;
        }
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }

    public TreeNode lowestCommonAncestor5(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor5(root.left, p, q);
        TreeNode right = lowestCommonAncestor5(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}